package ljl.alg.jianzhioffer.round2;

import java.util.*;

/**
 * 这个题有三种解法，
 * 其中我的解法属于老六
 * */
public class _48_longest_non_repeat_substring {
    
    /**
     * 这个到底是动态规划还是滑动窗口？
     * 动态规划能做吗？好像不能；就得滑动窗口
     *
     * abcda
     * 来个 set 记录所有字符
     * 来个队列记录每个字符顺序
     * 碰到重复的，先移除元素，直到从队列把字符移出去；
     * 再放到队列里
     * 每个字符都记录最大值
     *
     * 勉强算是做出来了了吧。。
     * */
    public int lengthOfLongestSubstring4(String s) {
        int max = 0;
        Set<Character> set = new HashSet<>();
        LinkedList<Character> q = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (set.contains(c)) {
                while (!q.isEmpty() && q.peekFirst() != c) {
                    set.remove(q.poll());
                }
                if (!q.isEmpty())
                    q.poll();
            } else {
                set.add(c);
            }
            q.offer(c);
            if (q.size() > max)
                max = q.size();
        }
        return max;
    }
    
    /*
    * 下面几个解法都要用动态规划
    * 原理是
    * dp[i] 表示 i 结尾的不包含重复字符的字符串的长度，那么，再来个字符
    * 如果这个字符 c，之前的位置 j，i - j > dp[i]，那说明没重复，dp[i] = dp[i - 1] + 1
    *
    * 如果重了，那 dp[i] = i - j
    *
    * 就这两种情况，然后！由于只和 dp[i - 1] dp[i] 有关，所以一个 tmp 变量就够了
    *
    * */
    /**
     * 动态规划 + 哈希表
     *
     * */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for (int i = 0; i < s.length(); i++) {
            int last = dic.getOrDefault(s.charAt(i), -1);
            dic.put(s.charAt(i), i);
            tmp = i - last > tmp ? tmp + 1 : i - last;
            res = Math.max(res, tmp);
        }
        return res;
    }
    
    /**
     * 线性遍历 + 哈希表
     *
     * */
    public int lengthOfLongestSubstring2(String s) {
        int res = 0, tmp = 0;
        for (int i = 0; i < s.length(); i++) {
            int last = i - 1;
            while (last >= 0 && s.charAt(i) != s.charAt(last)) last--;
            tmp = i - last > tmp ? tmp + 1 : i - last;
            res = Math.max(res, tmp);
        }
        return res;
    }
    
    /**
     * 怎么说呢！
     *
     * */
    public int lengthOfLongestSubstring3(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int old = -1, res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 这里获取当前字符上一个位置！
            if (dic.containsKey(c)) {
                // 为啥要求 max
                // 这个 old，不是一个字符的 old
                // 而是所有字符的 old 里最大的那个
                // 别想得那么简单！
                old = Math.max(old, dic.get(c));
            }
            dic.put(c, i);
            res = Math.max(res, i - old);
        }
        return res;
    }
}
